Nguyễn Văn Vĩnh sinh ngày 15 tháng 6 năm 1882 (30 tháng 4 âm lịch năm Nhâm Ngọ) tại số nhà 46 phố Hàng Giấy, Hà Nội. Cha là ông Nguyễn Văn Trực, nguyên quán làng Phượng Vũ, xã Phượng Dực, thuộc phủ Thường Tín, tỉnh Hà Đông (nay là huyện Phú Xuyên).

Do thời đó chưa có công trình thủy nông cống Đồng Quan nên quanh năm ngập nước, cánh đồng chiêm chỉ cấy được mỗi năm một vụ nên nhiều dân làng phải bỏ lên tỉnh sinh sống.

Hai vợ chồng ông Trực lên ở nhờ nhà họ hàng bên ngoại là vợ của ông nghè Phạm Huy Hổ ở số 46 phố Hàng Giấy, Hà Nội để kiếm sống. Gia đình ông Trực đông con, từ 1882 tới 1890 hai ông bà sinh được hai con trai là Nguyễn Văn Vĩnh và Nguyễn Văn Thọ cùng 5 người con gái. Một mình bà Trực mưu sinh bằng cách về các vùng quê mua hàng gánh ra chợ Đồng Xuân gần nhà bán. Để đỡ gánh nặng, ông Trực đã cho con cả Nguyễn Văn Vĩnh, lúc đó 8 tuổi đi làm nghề kéo quạt ở trường thông ngôn của Pháp ở Đình Yên Phụ, Hà Nội.

Trường thông ngôn Collège des Interprètes du Tonkin mở năm 1886, do một người Pháp nói thạo tiếng Việt tên là André d'Argence làm hiệu trưởng kiêm giáo viên quản lý. Phương pháp dạy chủ yếu là truyền khẩu, trường cũng có dạy A, B, C... để học viên tập đọc, tập viết tiếng Pháp và có dạy cả chữ quốc ngữ (hồi đó ở ngoài Bắc, chữ này mới chỉ được dùng trong phạm vi của các giáo hội).

Ngồi cuối lớp kéo quạt nhưng Nguyễn Văn Vĩnh chăm chú nghe giảng và học lỏm. Nhờ vậy, mà ông biết nói và viết được chữ Pháp khá thành thạo. Nhờ chăm chỉ và ham học nên được ông hiệu trưởng D’Argence đồng ý cho dự thi tốt nghiệp khi lớp học mãn khóa (1893) vào lớp thông ngôn tập sự ngạch Tòa công sứ cùng với 40 học sinh của khóa học, và đỗ thứ 12 khi mới 10 tuổi. Thầy d'Argence bèn đặc cách xin học bổng cho ông và nhận ông làm học sinh chính thức của khóa học tiếp theo, khóa thông ngôn tòa sứ khóa 1893-1895 (ngoài thầy d'Argence còn có ông Đỗ Đức Toại, thủ khoa khóa 1890, cùng dạy). Nguyễn Văn Vĩnh đỗ thủ khoa khóa này lúc 14 tuổi, được tuyển đi làm thông ngôn ở tòa sứ Lào Cai...